1. Field of the Invention
The invention relates to general purpose arithmetic logic units (ALUs), and in particular to an ALU utilizing a residue number system in performing arithmetic operations.
2. Related Art
The binary number system is the most widely used number system for implementing digital logic, arithmetic logic units (ALU) and central processing units (CPU). Binary based computers can be used to solve and process mathematical problems, where such calculations are performed in the binary number system. Moreover, an enhanced binary arithmetic unit, called a floating point unit, enhances the binary computers ability to solve mathematical problems of interest, and has become the standard for most arithmetic processing in science and industry.
However, certain problems exist which are not easily processed using binary computers and floating point units. One such class of problems involves manipulating and processing very large numbers. One example is plotting the Mandelbrot fractal at very high magnification. In order to plot the Mandelbrot fractal at high magnifications, a very long data word is required. Ideally, the Mandelbrot fractal plotting problem necessitates a computer with an extendable word size.
The main issue is that any real computer must be finite in size, and consequently the computer word size must be fixed at some limit. However, closer analysis reveals other contributing problems. One such problem is the propagation of “carry” bits during certain operations, such as addition and multiplication. Carry propagation often limits the speed at which an ALU can operate, since the wider the data word, the greater the path for which carry bits are propagated. Computer engineers have helped to reduce the effect of carry by developing carry look-ahead circuitry, thereby minimizing, but not eliminating, the effects of carry.
However, even the solution of implementing look-ahead carry circuits introduces its own limitations. One limitation is that look-ahead carry circuits are generally dedicated to the ALU for which they are embedded, and are generally optimized for a given data width. This works fine as long as the CPU word size is adequate for the problems of interest. However, once a problem is presented which requires a larger data width, the CPU is no longer capable of using its native data and instruction formats for direct processing of the larger data width.
In this case, computer software is often used to perform calculations on larger data widths by breaking up the data into smaller data widths. The smaller data widths are then processed by the CPU's native instruction set. In the prior art, software libraries have been written specifically for this purpose. Such libraries are often referred to as “arbitrary precision” math libraries. Specific examples include the arbitrary precision library from the GNU organization, and the high precision arithmetic library by Ivano Primi.
However, software approaches to processing very large data widths have significant performance problems, especially as the processed data width increases. The problem is that software processing techniques tend to treat the smaller data widths as digits, and digit by digit processing leads to a polynomial increase in execution time as the number of digits increases. In one example, an arbitrary precision software routine may take four times as much time to execute when the data width is doubled. When using arbitrary precision software solutions, the amount of processing time often becomes impractical.
One possible solution is to build a computer which is not based on binary arithmetic, and which does not require carry propagation logic. One candidate number system is the residue number system (RNS). Residue number addition, subtraction and multiplication do not require carry, and therefore do not require carry logic. Therefore, it is possible that RNS addition, subtraction and multiplication be very fast, despite the word size of the ALU. These facts have provided some interest for RNS based digital systems in the prior art; unfortunately, prior art RNS based systems are only partially realized, and have failed to match the general applicability of binary based systems in essentially every instance. This fact is evident from the lack of practical RNS based systems in the current state of the art.
The reasons for the failure of RNS based systems to displace binary systems are many. Fundamental logic operations, such as comparison and sign extension, are more complex in RNS systems than traditional binary systems, and require more logic circuitry and execution time. For many experts, it is often assumed the difficulty of RNS comparison, RNS to binary conversion, and RNS sign and digit extension make RNS based processors and ALUs impractical for general purpose processing.
In addition to the problems noted above, the lack of a practical RNS integer divide further restricts the applicability of RNS based systems of the prior art. Also, the lack of general purpose fractional number processing has (severely) restricted the usefulness of RNS based digital systems of the prior art. In summary, prior art RNS systems cannot process numbers in a general purpose manner, and this has relegated such systems to little more than research subjects.